
\documentclass[paper=a4, fontsize=11pt]{scrartcl} % A4 paper and 11pt font size

\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage{fourier} % Use the Adobe Utopia font for the document - comment this line to return to the LaTeX default
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm} % Math packages
\usepackage[UTF8]{ctex}
\usepackage{xcolor}
\usepackage{listings}
\usepackage{tikz}
\usepackage{lipsum} % Used for inserting dummy 'Lorem ipsum' text into the template
\usepackage{clrscode}
\usepackage{sectsty} % Allows customizing section commands
\usepackage[framed,numbered,autolinebreaks,useliterate]{mcode}
\usetikzlibrary{graphs}
\usetikzlibrary{shapes.arrows}
\allsectionsfont{\indent\normalfont\scshape} % Make all sections centered, the default font and small caps
\usepackage{indentfirst}
\setlength{\parindent}{2em}
\usepackage{fancyhdr} % Custom headers and footers
\pagestyle{fancyplain} % Makes all pages in the document conform to the custom headers and footers
\fancyhead{} % No page header - if you want one, create it in the same way as the footers below
\fancyfoot[L]{} % Empty left footer
\fancyfoot[C]{} % Empty center footer
\fancyfoot[R]{\thepage} % Page numbering for right footer
\renewcommand{\headrulewidth}{0pt} % Remove header underlines
\renewcommand{\footrulewidth}{0pt} % Remove footer underlines
\setlength{\headheight}{13.6pt} % Customize the height of the header

\numberwithin{equation}{section} % Number equations within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{figure}{section} % Number figures within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{0pt} % Removes all indentation from paragraphs - comment this line for an assignment with lots of text

\usepackage[top=2cm, bottom=2cm, left=2cm, right=2cm]{geometry}
\usepackage[linesnumbered,boxed,lined,ruled,vlined]{algorithm2e}
\usepackage{algorithmicx}
\usepackage{algpseudocode}

\usepackage{graphicx}
\usepackage{float}
%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------

\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height

\title{
\normalfont \normalsize
\textsc{中国科学院大学}\ \textsc{计算机与控制学院} \\ [25pt] % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge 算法设计与分析第三次作业 \\ % The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}

\author{黎吉国} % Your name

\date{\normalsize\today} % Today's date or a custom date

\begin{document}

\maketitle % Print the title

\newpage
\section{answer for 1st}
\textbf{问题分析:}\\
我们可以想象，那些情况是不能构成无向图的：
\begin{itemize}
\item  度数之和为奇数，则不可能构成无向图。
\item  假如$n$个节点中某个节点的度数超过了$n-1$，则不能构成无向图。
\end{itemize}
针对以上两个条件，我们可以为序列$d_1,d_2,\ldots,d_n$构造一个无向图：
\begin{itemize}
  \item 检查序列是否为偶数
  \item 将序列排序
  \item 选择最大的一个，判断其是否大于剩余序列的长度$(n-1)$，假如为$k$,
   如果不成立，则不能构造出无向图。否则，将接下来$k$个数减一，判断减一之后是否有负数，如果有，则不能构成无向图，
   否则，$n\leftarrow n-1$，循环执行该步骤，直至$n=0$.
\end{itemize}
\subsection{pseudo-code}
\begin{algorithm}
  \caption{exist-undirected-graph}
      \KwData{D: a list}
      \KwResult{IsExist: a bool data }
      \Begin{
        $D\_sum \leftarrow sum(D)$\\
        \If {$D\_sum$ is odd}
        {
            $IsExist=false$;\\
            \Return;\\
        }
          \For{$i=1:1:lenth\ of\ D$}
          {
              Sort D[i]-D[n] in descending.\\
              $k=D[i]$;\\
              \If{$k>n-i$}
              {
                $IsExist=false$;\\
                \Return;\\
              }
              \Else
              {
                \For{$j=i+1:1:i+k$}
                {
                    \If{$D[j]<1$}
                    {
                      $IsExist=false$;\\
                      \Return;\\
                    }
                    \Else
                    {
                        $D[j]--$;\\
                    }
                }
              }
          }
          $IsExist=true$;\\
      }
\end{algorithm}
\subsection{correction}
我们可以将节点的degree看做一种有限的资源，上面的算法中每次向资源最多的多个节点中获取资源，假如这样依然不能满足条件，则其他的获取方式更不能满足条件。
\subsection{time complexity}
排序的算法复杂度是$nlg(n)$，外面还有一层循环，则复杂度是$n^2lg(n)$。
\newpage
\section{answer for 4nd}
Suppose you are given two sets $A$ and $B$， each containing $n$ positive integers, You can choose to reorder each set however you like. After reordering, let $a_i$ be the $i$th element of set $A$,
and let $b_i$ be the $i$th element of set $B$. You then receive a payoff of $\Pi_{i=1}^{n}a_i^{b_i}$. Given an poltnomial-time algorithm that will maximize your payoff.\\
\textbf{问题分析：}\\
这是两个序列的组合问题，一共有$n!$种组合，我们可以假设一个序列是有序的，另一个序列是无须的，这样依然有$n!$中组合，这里我们假设$a_i$序列是升序的。
\begin{itemize}
  \item 问题规模为$n$时，问题太复杂。
  \item 当$n=2$时，不失一般性，假设$b_1<b_2$，有两种情况，我们比较两者的大小：(假设$a_i$是升序)
  \begin{align*}
    \frac{a_1^{b_1}a_2^{b_2}}{ a_1^{b_2}a_2^{b_1} }=\frac{ a_2^{b_2-b_1} }{ a_1^{b_2-b_1} }=(\frac{a_2}{a_1})^{b_2-b_1}>1
  \end{align*}
  所以，我们可以通过交换$b_i$序列中的逆序对来增大收益。最终的结果是，$b_i$是一个和$a_i$一样的升序。
\end{itemize}
\subsection{pseudo-code}
\begin{algorithm}
  \caption{exist-undirected-graph}
      \KwData{A,B: two sets containing n positive integers}
      \KwResult{payoff: total payoff}
      \Begin{
        Sort A,B in the increasing order.\\
        $payoff=1$;\\
        $n=length(A);$\\
        \While{$n>0$}
        {
          $payoff = payoff * A[n]^{B[n]};$\\
          $n--;$\\
        }
      }
\end{algorithm}
\subsection{Correction}
Suppose that $a_i$ is in the increasing order. there is a property:
\begin{itemize}
  \item if $i<j$ and $b_i>b_j$, we can switch $b_i$ and $b_j$ to get  a higher payoff.
\end{itemize}
So if $b_i$ is not in the increasing order, it must not be the optimal solution.

\subsection{Time Complixty}
两次排序，一层循环：$T(n)=2nlg(n)+n=O(nlgn)$.

\newpage
\section{answer for 5th}
Write a program in your favorite language to compress a file using Huffman code and then decompress it.
Code information may be contained in the comjpressed file if you can, use your program to compress the two file
( graph.txt and Aesop\_Fables.txt) and compare the results (Huffman code and compression ratio).

\subsection{pseudo-code}
\begin{algorithm}
  \caption{Huffman-Encode}
      \KwData{raw data}
      \KwResult{huffman data}
      \Begin{
        count the each character of raw data.\\
        use the count to generate a huffman tree.\\
        get the huffman code according to the huffman tree.\\
        compress the raw data.\\
      }
\end{algorithm}
\begin{algorithm}
  \caption{Huffman-decode}
      \KwData{huffman data}
      \KwResult{raw data}
      \Begin{
        read the huffman code.\\
        use the huffman code to generate a huffman tree.\\
        decompress the huffman data using the huffman tree.\\
      }
\end{algorithm}
\subsection{test result}
\lstset{language=C++}%代码语言使用的是matlab
\lstset{breaklines}%自动将长的代码行换行排版
\lstset{extendedchars=false}%解决代码跨页时，章节标题，页眉等汉字不显示的问题\
\textbf{For file "graph.txt"}
\begin{lstlisting}[frame=single]
  last compression infomation
  raw file size:          2094720
  huffman data size:      930329
  compression ratio(data):0.55587
  file head size:         1378
  compression ratio(file):0.555212
\end{lstlisting}
\textbf{Huffman code:}
\begin{lstlisting}[frame=single]
  160:111
  163:0100001001
  172:010001001100
  174:01000101100
  176:01001
  177:00
  178:1100
  179:1010
  180:1001
  181:0110
  182:0111
  183:0101
  184:1011
  185:1000
  186:01000100100
  187:010001011011
  197:010000010001
  198:0100010011010
  211:0100010011011
  212:01000001001
  225:01000110110
  227:0100011010
  228:010001010
  229:01000111
  230:0100001000
  231:010000011
  232:010000101
  233:01000000
  236:0100010001
  237:01000110111
  238:010001100
  239:010000111
  240:01000100101
  242:0100010000
  243:0100010111
  244:010000110
  245:0100000101
  246:010001011010
  247:01000100111
  249:010000010000
\end{lstlisting}
\textbf{For file " Aesop\_Fables.txt"}
\begin{lstlisting}[frame=single]
  last compression infomation
  raw file size:          190066
  huffman data size:      108372
  compression ratio(data):0.429819
  file head size:         1727
  compression ratio(file):0.420733
\end{lstlisting}
\textbf{Huffman code:}
\begin{lstlisting}[frame=single]
138:101100
141:101101
160:111
161:110100101101
162:10011111
167:11010010101
168:01000101100100
169:01000101100101
172:011111
173:11010010100
174:0111101
176:100111010101101
177:0100010110011
178:0100010110000
179:0100010110001
180:11010010110011
181:1001110101010
182:11010010110010
183:10011101010111
184:110100101100000
185:110100101100001
186:11010010011
187:11010010010
191:10011110110
193:01111001
194:1001111010
195:1001110110
196:0100010111
197:011110001
198:010000110
199:11010010111
200:100111100
201:01000010
202:01000011100
203:100111101111
204:010001000
205:010001001
206:1101001000
207:011110000
208:1001110111
209:1001110101011000
210:1001110100
211:100111001
212:0100000
213:100111101110
214:100111010100
215:100111000
216:11010010110001
217:01000101101
218:1001110101011001
225:1000
226:1101000
227:100100
228:11000
229:001
230:101111
231:100101
232:0101
233:0000
234:10011101011
235:11010011
236:01110
237:101110
238:0001
239:0110
240:010010
241:0100001111
242:11001
243:11011
244:1010
245:110101
246:0100011
247:100110
248:010001010
249:010011
250:01000011101
\end{lstlisting}
\subsection{compare the sesult}
相比来说，“graph.txt”的压缩率更高，究其原因，是因为其中的字符的分布不均匀，这样就可以使用较短的编码来表示出现频率更高的字符，达到较高的压缩效率。
\end{document}
